\chapter{Calling conventions}
\label{chap-calling-conventions}

In this chapter, we describe the \sysname{} calling conventions that
are common for all native backends.  We describe only the
\emph{default} calling conventions, i.e., the calling conventions that
are applicable when an unknown callee is invoked.  The call-site
manager described in \refChap{chap-call-site-manager} will tailor the
calling conventions for each pair caller/callee when the callee is
known. 

We do not use callee-saves registers.  They complicate the calling
conventions, and especially the stack-traversal code of the garbage
collector.  And the default calling conventions do not use registers
to pass arguments.  Using the default calling conventions, the callee
must parse the arguments, and this task might involve looping over all
arguments to determine keyword arguments.  This task is simplified if
all arguments are passed on the stack.

\section{Normal call}

\subsection{Caller action before call}
\label{sec-caller-action-before-call}

The caller starts by setting up the callee stack frame as
shown in \refFig{fig-initial-callee-stack-frame}.

\begin{figure}
\begin{center}
\inputfig{fig-initial-callee-stack-frame.pdf_t}
\end{center}
\caption{\label{fig-initial-callee-stack-frame}
Callee stack frame set up by caller.}
\end{figure}

The callee stack frame does not evolve during the invocation of the
callee, or in other words, the stack frame set up by the caller
contains all the lexical variables that can not be kept in registers,
and for the duration of the invocation of the callee.

The slot marked ``unused'' in \refFig{fig-initial-callee-stack-frame}
is reserved for the return address, should the callee need to save it.
The callee frame pointer is set last, since the caller needs its frame
pointer to initialize every other slot, including the arguments.  The
size of the callee stack frame is taken from the callee function
object.  Arguments are in reverse order, i.e., the last argument is on
top of the stack.

Once the callee stack frame has been set up, the caller
executes an instruction that transfers control to the callee and saves
the return address.  On some backends, the return address is then
pushed on top of the stack.  On such backends, the callee pops the
return address and stores it in the slot marked ``unused'' in
\refFig{fig-initial-callee-stack-frame}.  On some backends, the return
address is saved in a register.  On such backends, the callee just
saves the contents of that register in the ``unused'' slot.

\subsection{Callee action to parse arguments}

The callee can determine the number of supplied arguments by using the
size of its stack frame (which is computed by the compiler), the frame
pointer, and the stack pointer.  It parses the arguments according to
its lambda list, and stores parameter values in registers or in the
stack frame.  It then removes the arguments from the top of the stack,
giving the situation shown in
\refFig{fig-callee-stack-frame-after-argument-parsing}.

\begin{figure}
\begin{center}
\inputfig{fig-callee-stack-frame-after-argument-parsing.pdf_t}
\end{center}
\caption{\label{fig-callee-stack-frame-after-argument-parsing}
Callee stack frame after argument parsing.}
\end{figure}

\subsection{Callee action to return values}

The callee returns values on top of the stack, in the same order as
arguments are passed.  It removes the call-site descriptor, and it
puts the caller frame pointer in an agreed-upon register.  Depending
on the backend, it puts the return address either in a register or on
top of the stack according to how the \texttt{return} instruction on
the backend works.

The difference between the callee frame pointer and the callee stack
pointer determines the number of return values.  The first return
value is returned in an agreed-upon register.  If there are zero
return values, this register contains \texttt{nil}.  Otherwise, the
stack holds return values beyond the first one, but there is still a
slot on the stack for the first one.  The caller can save the first
return value in that slot, should it be required.

Once the return values have been put in their places, the callee
returns to the caller.

\subsection{Caller action to process return values}

The caller starts by copying the agreed-upon register in which the
callee put the caller frame pointer to the frame point.  This must be
done first so that the caller can then use its frame pointer to access
its own lexical variables.

The caller can either have stored a copy of its stack pointer in a
lexical variable, or it can use its statically known knowledge about
its own stack-frame size to determine its old value of the stack
pointer.  Return values are located on the stack in the locations
determined by this value and the current value of the frame pointer,
except the first return value which is located in an agreed-upon
register.

If a single return value is needed, then the caller accesses this
value in the agreed-upon register.  It then copies the old value of
the stack pointer to the stack pointer to remove the return values
from the stack.  The function call is now complete.

If multiple values are needed by the caller, then see below for how
these values are handled.

\section{Handling multiple return values}

Multiple values can be created only as a result of a function call.
The different ways multiple return values can be consumed is described
in the next section.

\subsection{Consumers of multiple values}

The following operators consume multiple values:

\begin{itemize}
\item \texttt{multiple-value-call}
\item \texttt{multiple-value-bind}
\item \texttt{multiple-value-setq}
\item \texttt{multiple-value-list}
\item \texttt{setf} with \texttt{values}
\end{itemize}

\subsubsection{\texttt{multiple-value-call}}

This operator can be seen as the most basic consumer of multiple
values.

\subsubsection{\texttt{multiple-value-bind}}

The standard says that

\begin{verbatim}
(multiple-value-bind ({var}*) values-form {form}*)
\end{verbatim}

is equivalent to

\begin{verbatim}
(multiple-value-call
    (lambda (&optional {var}* &rest #1=:ignore)
      (declare (ignore #1#))
      {form}*)
  values-form)
\end{verbatim}

Provided that a \texttt{\&rest} variable that is unused in the
function body is handled by not allocating a list of the remaining
arguments, this definition is not too bad.  Clearly,
\texttt{multiple-value-bind} must check the number of arguments, and
initialize optional parameters with \texttt{nil} when a corresponding
argument is omitted.  This is the same work as the anonymous function
in the second code snippet does.

\subsubsection{\texttt{multiple-value-setq}}

The standard says that

\begin{verbatim}
(multiple-value-setq ({symbol}*) values-form)
\end{verbatim}

Is defined to behave the same way as

\begin{verbatim}
(values (setf (values {symbol}*) values-form))
\end{verbatim}

where the outermost \texttt{values} is there to make sure that a
single value is returned, as the standard requires. 

\subsubsection{\texttt{multiple-value-list}}

The standard says that

\begin{verbatim}
(multiple-value-list values-form)
\end{verbatim}

is equivalent to

\begin{verbatim}
(multiple-value-call #'list values-form)
\end{verbatim}

It is very likely that allocating the \texttt{cons} cells that make up
the list will dominate over the use of the default calling convention,
so this equivalent form can be used without optimization. 

\subsubsection{\texttt{setf} with \texttt{values}}

According to the standard, \texttt{setf} with \texttt{values} binds
the variables ``as if by \texttt{multiple-value-bind}'', and this is
also a reasonable implementation.  Since \texttt{multiple-value-bind}
is defined in terms of \texttt{multiple-value-call}.  Therefore, all
operators that consume multiple values can be reduced to
\texttt{multiple-value-call}.

\subsection{Implementing \texttt{multiple-value-call}}
\label{sec-implementing-multiple-value-call}

The arguments to \texttt{multiple-value-call} are computed
left-to-right as usual.

\subsubsection{Caller when the callee has been computed}

When the first argument, i.e., the function to call, is computed, it
is not just stored in a temporary location as with an ordinary call.
Instead, the caller immediately initializes the callee stack frame.
To do that, it first saves a copy of the current stack pointer in a
lexical variable.  It then subtracts from its stack pointer the amount
required by the callee lexical variables, the saved caller stack
frame, the return address, and the call-site descriptor.

\subsubsection{Handling each additional argument}

Each additional argument is computed in a context that requires
all values computed.  If the argument is either a variable or a
literal, then its value is pushed on the stack.  If not, computing the
argument ultimately results in a function call.  

For each argument, the caller saves a copy of the current stack
pointer in a lexical variable.  If the argument is a function call,
then it is handled as usual\footnote{The call is subject to
  optimization by the call-site manager as describe in
  \refChap{chap-call-site-manager}}, and multiple values, except the
first one, are returned on the stack.  The first return value
(provided that there is at least one return value) is copied to its
reserved location on the stack, using the saved copy of the current
stack pointer.

When each argument has been computed, the callee stack frame and the
arguments to be passed to the callee are correctly placed on the
stack.  The caller now stores its own frame pointer and the call-site
descriptor in the ordinary locations in the callee stack frame.  It
then initializes the callee frame pointer by using its saved copy of
the initial stack pointer.  It then calls the callee as with an
ordinary function call.

\subsection{Transfer of multiple values to an exit point}

To be filled in.

\section{Tail call}

For a tail call, the caller must replace its own stack frame with the
callee stack frame and the arguments as shown in
\refFig{fig-initial-callee-stack-frame}.  The caller frame pointer,
the return address, and the call-site descriptor do not change.

As with a normal call, the function object and the arguments are first
computed and stored in temporary locations, either on the stack or in
registers.

When the callee stack frame is at least as large as the caller stack
frame, the situation is relatively simple.  The arguments to pass are
all outside the stack frame of the caller, so the caller can just
subtract an appropriate amount from the stack pointer, and store the
arguments in the place where the callee expects them.  When the callee
stack frame is smaller than the caller stack frame, some, perhaps all,
arguments must be put in locations that are currently inside the
caller stack frame.  However, the number of arguments can not be
greater than the number of slots in the caller stack frame plus the
number of registers available, and the compiler can allocate a larger
stack frame for the caller so that there are additional slots or
additional registers available.

The caller can then store the arguments one at a time in any order.
For each argument, the following action is taken:

\begin{enumerate}
\item If the slot for the argument to place contains another argument
  that has not yet been placed, that other argument is first moved to
  a temporary location.
\item The argument to place is then put in the corresponding stack
  slot.  This action will free up the temporary location into which
  the argument was originally computed, thereby preserving the number
  of temporary locations available.
\end{enumerate}


% LocalWords:  callee
